package cn.zzf.leetcode;


public class T0010_IsMatch {

    public static boolean isMatch1(String s, String p) {
        char[] pa = p.toCharArray();
        char[] sa = s.toCharArray();
        int pi = pa.length + 1;
        int si = sa.length + 1;
        boolean[][] dp = new boolean[pi][si];
        dp[0][0] = true;
        for (int j = 1; j < si; j++) {
            for (int i = 1; i < pi; i++) {
                char pc = pa[i - 1];
                char sc = sa[j - 1];
                boolean lastMatch = dp[i - 1][j - 1];
                if (pc != '*') {
                    dp[i][j] = lastMatch && (sc == pc || pc == '.');
                } else {
                    // 匹配0个
                    if(dp[i][j - 2]) dp[i][j] = true;

                    // 匹配一个或多个
                    if (lastMatch) {
                        char lastPc = pa[i - 2];
                        char lastSc = sa[j - 2];
                        if (lastPc == '.' || lastPc == lastSc) {
                            dp[i][j] = true;
                        }
                    } else {
                        dp[i][j] = false;
                        break;
                    }
                }
            }
        }
        return dp[pa.length][sa.length];
    }

    public static void main(String[] args) {
        System.out.println(isMatch1("aaa", "a*a"));
        System.out.println(isMatch1("aa", "a"));
        System.out.println(isMatch1("mississippi", "mis*is*ip*."));
        System.out.println(isMatch1("aava", "av*av*a"));
    }

}
